package org.aplombh.java.awcing.basic.dp.intervalDP;

import javafx.util.Pair;

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * 设有 N 堆石子排成一排，其编号为 1，2，3，…，N。
 * <p>
 * 每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。
 * <p>
 * 每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
 * <p>
 * 例如有 4 堆石子分别为 1 3 5 2， 我们可以先合并 1、2 堆，代价为 4，得到 4 5 2， 又合并 1，2 堆，代价为 9，得到 9 2 ，再合并得到 11，总代价为 4+9+11=24；
 * <p>
 * 如果第二步是先合并 2，3 堆，则代价为 7，得到 4 7，最后一次合并代价为 11，总代价为 4+7+11=22。
 * <p>
 * 问题是：找出一种合理的方法，使总的代价最小，输出最小代价。
 * <p>
 * 输入格式
 * 第一行一个数 N 表示石子的堆数 N。
 * <p>
 * 第二行 N 个数，表示每堆石子的质量(均不超过 1000)。
 * <p>
 * 输出格式
 * 输出一个整数，表示最小代价。
 * <p>
 * 数据范围
 * 1≤N≤300
 * 输入样例：
 * 4
 * 1 3 5 2
 * 输出样例：
 * 22
 */
public class MergeStone_282 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(reader.readLine());
        MergeStone ms = new MergeStone(n);
        String[] str = reader.readLine().split(" ");
        for (int j = 1; j <= n; j++) {
            ms.s[j] = Integer.parseInt(str[j - 1]);
            ms.s[j] += ms.s[j - 1];
        }
        System.out.println(ms.solve());
    }
}

class MergeStone {
    public static final int N = 310;
    int n;
    int[] s = new int[N];
    int[][] f = new int[N][N];
    int[][] path = new int[N][N];

    public MergeStone(int n) {
        this.n = n;
    }

    public int solve() {
        for (int len = 2; len <= n; len++) { // 长度
            for (int i = 1; i + len - 1 <= n; i++) { // i 区间起始位置，要减len
                int j = i + len - 1; // j 区间结束位置，
                f[i][j] = 1 << 30;
                for (int k = i; k < j; k++) { // k:区间中间分隔点
                    if (f[i][j] > f[i][k] + f[k + 1][j] + s[j] - s[i - 1]) {
                        path[i][j] = k;
                    }
                    f[i][j] = Math.min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);

                }
            }
        }

        ArrayList<String> info = new ArrayList<>();
        Pair<Integer, Integer>[] e = new Pair[N];
        int head = 0;
        int tail = -1;

        int i = 1, j = n;

        e[++tail] = new Pair<>(i, path[i][j]);
        e[++tail] = new Pair<>(path[i][j] + 1, j);


        info.add(i + "->" + path[i][j] + " " + (path[i][j] + 1) + "->" + j);

        while (head <= tail) {
            Pair<Integer, Integer> t = e[head++];
            i = t.getKey();
            j = t.getValue();

            info.add(i + "->" + path[i][j] + " " + (path[i][j] + 1) + "->" + j);

            if (i < j) {
                if (i + 1 < path[i][j])
                    e[++tail] = new Pair<>(i, path[i][j]);
                if (path[i][j] + 2 < j)
                    e[++tail] = new Pair<>(path[i][j] + 1, j);
            }
        }

        for (i = info.size() - 1; i >= 0; i--) {
            System.out.println(info.get(i));
        }

        return f[1][n];
    }
}